package leetcode_day._2021._202108._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/8/13 12:11
 * 数字 1 的个数
 * 算法：数学
 * 枚举 n 的每一位，12345
 *
 * n 的第 2 位为 3
 *
 * 1 的个数由这两部分组成
 *
 * - 左边部分能够取值的范围为 [0, 11]，右边随便取，范围为 [0, 99]，有 12 * 100 种
 * - 当左边部分为 12 时，由于 3 > 1，所以右边随便取，范围为 [0, 99]，有 100 种
 *   - 当前位的数小于 1 时，右边部分为 0
 *   - 等于 1 时，右边部分的范围为 [0, max]，有 max + 1 种
 *   - 大于 1 时，右边部分的范围为 [0, 99]，有 100 种
 */
public class _13_233 {
    public static void main(String[] args) {
        System.out.println(new _13_233().countDigitOne(13));

    }

    public int countDigitOne(int n) {
        int ans = 0;
        // 按位遍历
        for (long i = 1; i <= n; i *= 10) {
            // n / (i * 10) 是当前位左边部分的数字
            ans += n / (i * 10) * i;
            // 当前位上的数
            long x = (n / i) % 10;
            // 如果 x 比 1 大，就随便取，总共有 i 种
            // n % i 表示当前位右边部分的数字，+1 表示总共有几种
            // 当 x == 1 时，就有 n % i + 1 种
            // 当 x == 0 时，有 0 种，*x 就是为了这种情况
            ans += x > 1 ? i : (n % i + 1) * x;
        }
        return ans;
    }

}
